home *** CD-ROM | disk | FTP | other *** search
/ Atari Mega Archive 2 / Atari Mega Archive CD - Volume 2.iso / 8bit / cislib_b / sort.doc < prev    next >
Text File  |  1995-04-22  |  5KB  |  199 lines
  1.                 SORT 
  2.  
  3.    SORT is a high performance in-RAM 
  4. ACTION! sorting FUNCtion.  It is 
  5. restricted to fixed length entries 
  6. with a single key, although the key 
  7. can be any length and located 
  8. anywhere within the entry.  SORT 
  9. features compact size and great 
  10. flexibility, while being very easy to 
  11. use. 
  12.  
  13.    TYPICAL PERFORMANCE (SECONDS) 
  14.  
  15.  ********************************** 
  16.  *     Length:|  8 | 32 | 128| 512* 
  17.  ********************************** 
  18.  *  32 Entries|0.05|0.12|0.37|1.40* 
  19.  *------------+----+----+----+----* 
  20.  *  64 Entries|0.13|0.30|1.00|3.77* 
  21.  *------------+----+----+----+----* 
  22.  * 128 Entries|0.32|0.77|2.60| N/A* 
  23.  *------------+----+----+----+----* 
  24.  * 256 Entries|0.77|1.90|6.45| N/A* 
  25.  *------------+----+----+----+----* 
  26.  * 512 Entries|1.85|4.58| N/A| N/A* 
  27.  *------------+----+----+----+----* 
  28.  *1024 Entries|4.53|11.4| N/A| N/A* 
  29.  *------------+----+----+----+----* 
  30.  *2048 Entries|10.8| N/A| N/A| N/A* 
  31.  *------------+----+----+----+----* 
  32.  *4096 Entries|25.8| N/A| N/A| N/A* 
  33.  ********************************** 
  34.    (All timings for SORT are the 
  35. arithmetic mean of 16 runs with fully 
  36. random numeric data, sorting on the 
  37. entire entry, with display DMA 
  38. enabled in TEXT MODE 0.  Timings are 
  39. to the nearest 1/60 second using the 
  40. ATARI Real-Time CLOcK.  Performance 
  41. may be significantly improved or 
  42. degraded with non-random data and/or 
  43. different display DMA.) 
  44.  
  45.    COMPARISON TO SUPERSORT 
  46. (APX-20030) 
  47.  
  48.    As compared to "SUPERSORT", SORT 
  49. has several major advantages, 
  50. particularly for the ACTION! user, 
  51. and only two disadvantages.  The 
  52. first disadvantage is slight: 
  53. although SORT is quite fast, 
  54. apparently it is a little bit slower 
  55. than "SUPERSORT".  (Whereas 
  56. "SUPERSORT" claims to sort 1000 
  57. thirty-byte entries in "less than ten 
  58. seconds", SORT will typically take 
  59. about 10.5 seconds.  For 1000 
  60. one-byte entries, the comparison is 
  61. "less than two seconds" versus 
  62. typically about 2.27 seconds.  But 
  63. see timing note above.)  The second 
  64. disadvantage is that SORT is limited 
  65. to sorting on a single key (although 
  66. that key may be located anywhere in 
  67. the entry and may be of any length), 
  68. whereas "SUPERSORT" can handle 
  69. multiple keys. 
  70.    On the other hand, the advantages 
  71. of SORT are several: 
  72.    1.  About one-third the storage 
  73. requirement.  (356 bytes versus 
  74. "about" 1000 bytes, plus no use of 
  75. RAM page 6 - see #4 below) 
  76.    2.  Does not use "AUTORUN.SYS" or 
  77. install itself automatically. 
  78. Instead, SORT is an ACTION! FUNCtion 
  79. which may be INCLUDEd from a library. 
  80. (This frees "AUTORUN.SYS" for other 
  81. purposes, saves precious RAM, and 
  82. prevents conflict with use of the 
  83. ATARI 850 Interface Module.) 
  84.    3.  Error checking to prevent 
  85. inadvertant RAM alteration. 
  86.    4.  No use of page 6 in memory. 
  87. (Instead, SORT uses only the floating 
  88. point work area $D4-$DF and the 6502 
  89. stack, saving page 6 for other 
  90. purposes). 
  91.    5.  "Unlimited" entry length 
  92. (versus 256 bytes). 
  93.    6.  "Unlimited" number of entries 
  94. (versus 10000). 
  95.    7.  No POKE statements required. 
  96. (All parameters are passed by the 
  97. ACTION! FUNCtion call.) 
  98.  
  99.    IMPORTANT NOTES 
  100.  
  101.    1.  Since the location of the sort 
  102. key may be anywhere in the entry, it 
  103. is possible to sort the same data 
  104. again in a different sequence. 
  105.    2.  For equal keys, SORT does NOT 
  106. preserve the original entry sequence 
  107. (so it WON'T work for successive 
  108. sorts on separate minor to major keys 
  109. - you must sort on a single composite 
  110. key). 
  111.  
  112.    CALLING 
  113.  
  114. BYTE FUNC Sort(CARD KPOS, KLEN, ELEN, 
  115. DLEN, BYTE POINTER DADR) 
  116.  
  117.    KPOS:  The position of the most 
  118. significant byte of the sort key 
  119. within the entry.  (The first 
  120. position of the entry is 0.) 
  121.    KLEN:  Length of the sort key. 
  122.    ELEN: Length of individual entries 
  123. within the array (or block of RAM). 
  124. DLEN must be evenly divisible by 
  125. ELEN! 
  126.    DLEN:  Length of the array (or 
  127. block of RAM). 
  128.    DADR:  Address of the array (or 
  129. block of RAM) containing all of the 
  130. data to be sorted. 
  131.  
  132.    RETURN CODE 
  133.  
  134.    SORT returns 0 if the sort was 
  135. successful, 1 if the parameters were 
  136. in error. 
  137.  
  138.    ALGORITHM 
  139.  
  140.    SORT is a 6502 machine language 
  141. adaptation of the shell sort 
  142. algorithm as discussed by D. E. Knuth 
  143. in "The Art of Computer Programming, 
  144. Vol. 3: Sorting and Searching" 
  145. (Addison-Wesley, Reading, Mass., 
  146. 1973). 
  147.  
  148.    DEMONSTRATION 
  149.  
  150.    The following ACTION! program will 
  151. read in a list of typed names, sort 
  152. them into alphabetical order, and 
  153. then display them on the screen: 
  154.  
  155. INCLUDE "SORT.ACT" 
  156. PROC DEMO() 
  157. BYTE ARRAY X(1000), ;50 X 20 BYTES 
  158.  S(21) ;I/O BUFFER 
  159. INT I,J 
  160. PRINTE("BLANK LINE TO END.") 
  161. FOR I=0 TO 1000-20 STEP 20 
  162. DO 
  163.  PRINT("NAME: ") 
  164.  INPUTMD(0,S,20) 
  165.  IF S(0)=0 THEN EXIT 
  166.  ELSEIF S(0)<20 THEN 
  167.   SETBLOCK(S+S(0)+1,20-S(0),' ) 
  168.  FI 
  169.  MOVEBLOCK(X+I,S+1,20) 
  170. OD 
  171. IF SORT(0,20,20,I,X) THEN 
  172.  PRINTE("SORT ERROR!") BREAK() FI 
  173. FOR J=0 TO I-20 STEP 20 
  174. DO 
  175.  MOVEBLOCK(S+1,X+J,20) 
  176.  S(0)=20 
  177.  PRINTE(S) 
  178. OD 
  179. RETURN 
  180.  
  181.  
  182.  
  183.  
  184.  
  185.  
  186.  
  187.  
  188.  
  189.  
  190.  
  191.  
  192.  
  193.  
  194.  
  195.  
  196.  
  197.  
  198.  
  199.